#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        while (cur || !st.empty()) {
            while (cur) {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            if (cur->right == nullptr || pre == cur->right) {
                ans.push_back(cur->val);
                pre = cur;
                cur = nullptr;
            }
            else {
                st.push(cur);
                cur = cur->right;
            }
        }
        return ans;
    }
};

